package com.itheima.datastructure.linkedlist;

import java.util.Iterator;

/**
 * @author tantao
 * @version 1.0
 * @description: 双向链表
 * @date 2025/8/6 14:29
 */
public class DoublyLinkedListSentinel01<T> implements Iterable<T> {


    @Override
    public Iterator<T> iterator() {
        return new Iterator<T>() {
            Node<T> p = head.next;

            @Override
            public boolean hasNext() {
                return p != tail;
            }

            @Override
            public T next() {
                T value = p.value; // 返回当前节点的数据
                p = p.next; //并指向下一个元素
                return value;
            }
        };
    }

    static class Node<T> {
        //前驱节点
        public Node prev;
        //数据
        public T value;
        //后继节点
        public Node next;

        public Node(Node prev, T value, Node next) {
            this.prev = prev;
            this.value = value;
            this.next = next;
        }

        @Override
        public String toString() {
            return "Node{" + value + "}";
        }
    }

    private Node head; // 头哨兵
    private Node tail; // 尾哨兵

    public DoublyLinkedListSentinel01() {
        head = new Node(null, "HEAD", null);
        tail = new Node(null, "TAIL", null);

        // 初始化 头->尾 尾->头
        head.next = tail;
        tail.prev = head;
    }


    public void addFirst(T value) {
        insert(0, value);
    }


    public void removeFirst() {
        remove(0);

    }

    public void addLast(T value) {
        Node prev = tail.prev;
        Node added = new Node(prev, value, tail);

        prev.next = added;
        tail.prev = added;

    }

    public void removeLast() {
        Node removed = tail.prev;
        if (removed == head) {
            throw illegalIndex(0);
        }
        Node prev = removed.prev;
        prev.next = tail;
        tail.prev = prev;

        removed.prev = null;
        removed.next = null;
    }


    /**
     * | current |
     * | prev | next |
     * | prev | current | next |
     *
     * @param index index
     * @param value value
     */
    public void insert(int index, T value) {
        checkIndex(index);
        //将新得节点插入到 prev和next之间
        Node prev = findNode(index - 1);
        if (null == prev) {
            throw illegalIndex(index);
        }
        Node next = prev.next;
        Node inserted = new Node(prev, value, next);
        prev.next = inserted;
        next.prev = inserted;
    }


    public void remove(int index) {
        checkIndex(index);
        Node removed = findNode(index);
        if (null == removed) {
            throw illegalIndex(index);
        }
        Node prev = removed.prev;
        Node next = removed.next;

        prev.next = next;
        next.prev = prev;


        // 删除节点
        removed.prev = null;
        removed.next = null;
    }

    private void checkIndex(int index) {
        if (index < 0) {
            throw illegalIndex(index);
        }
    }


    //找到第 index 个节点 （-1 则返回头哨兵）
    public Node findNode(int index) {
        int i = -1;
        for (Node p = head; p != tail; p = p.next, i++) {
            if (i == index) {
                return p;
            }
        }
        return null;

// -------------while-----------
//        int i = -1;
//        Node p = head;
//
//        // 使用 while 循环遍历链表
//        while (p != tail) {
//            if (i == index) {
//                return p;
//            }
//            p = p.next;
//            i++;
//        }
//
//        return null;
    }


    private IllegalArgumentException illegalIndex(int index) {
        return new IllegalArgumentException(
                String.format("index [%d] 不合法%n", index));
    }

    public static void main(String[] args) {
        DoublyLinkedListSentinel01 doublyLinkedListSentinel01 = new DoublyLinkedListSentinel01();
        System.out.println(doublyLinkedListSentinel01.findNode(-1));
    }


}
